from utilities import inside, y_intersection, intersection_point
from bisect import bisect, insort

def lsi(S):
    Q = []
    for i, s in enumerate(S):
        Q.append((s.upper, i+1))
        Q.append((s.lower, -(i+1)))
    comp = lambda x, y: cmp(x[0], y[0])
    Q = sorted(Q, comp)
    T = []
    I = []
    while Q != []:
        p, i_seg = Q[0]
        Q[:] = Q[1:]
        if i_seg > 0:
            T_aux = []
            for i_t in T:
                t = S[i_t]
                T_aux.append(y_intersection(t, p.y))
            ind = bisect(T_aux, p.x)
            T.insert(ind, i_seg-1)
            
            if ind > 0:
                left_intersection = intersection_point(S[T[ind]], S[T[ind-1]])
                if left_intersection != -1 and left_intersection.y < p.y:
                    I.append(left_intersection)
                    insort(Q, (left_intersection, 0))
            if (ind+1) < len(T):
                right_intersection = intersection_point(S[T[ind]], S[T[ind+1]])
                if right_intersection != -1  and right_intersection.y < p.y:
                    I.append(right_intersection)
                    insort(Q, (right_intersection, 0))
                    
        if i_seg < 0:
            ind = T.index(-(i_seg+1))
            T[:] = T[:ind] + T[ind+1:]
            if ind > 0 and ind < len(T): 
                intersection = intersection_point(S[T[ind-1]], S[T[ind]])
                if intersection != -1 and intersection.y < p.y:
                    I.append(intersection)
                    insort(Q, (intersection, 0))

        if i_seg == 0:
            C = []
            for i, i_t in enumerate(T):
                t = S[i_t]
                if inside(p, t):
                    C.append((i, i_t))
            beg = C[0][0]
            end = C[-1][0]
            T[beg:end+1] = reversed(T[beg:end+1])
            if beg > 0:
                left_intersection = intersection_point(S[T[beg]], S[T[beg-1]])
                if left_intersection != -1 and left_intersection.y < p.y:
                    I.append(left_intersection)
                    insort(Q, (left_intersection, 0))
            if (end+1) < len(T):
                right_intersection = intersection_point(S[T[end]], S[T[end+1]])
                if right_intersection != -1 and right_intersection.y < p.y:
                    I.append(right_intersection)
                    insort(Q, (right_intersection, 0))

    return I


def lsi2(S):
    Q = []
    for i, s in enumerate(S):
        Q.append((s.upper, i+1))
        Q.append((s.lower, -(i+1)))
        T = []
    comp = lambda x, y: cmp(x[0], y[0])
    Q = sorted(Q, comp)
    I = []
    while Q != []:
        event = Q[0]
        Q[:] = Q[1:]
        handle_point(event, S, Q, T, I)


def handle_point(event, S, Q, T, I):
    p, i_seg = event
    # TODO: Lo que sigue esta mal, no considera
    # multiples segmentos que empiecen en el
    # mismo punto
    U = []
    if i_seg > 0:
        U.append(S[i-1])
    # TODO: Lo que sigue deberia hacerse con busqueda
    # binaria, no secuencial. Es lo que hace que
    # no sea cuadratico cuando hay multiples segmentos
    # mas o menos a la misma altura, pero por ahora
    # lo hago secuencial
    L = []
    C = []
    for i_t in T:
        t = S[i_t]
        if t.lower == p:
            L.append(t)
        elif inside(p, t):
            C.append(t)
    if (len(L) + len(C) + len(U)) > 1:
        I.append((p, L+C+U))
    


    
